package containers

import "fmt"
import "container/list"

type treeNode struct {
	v     int
	left  *treeNode
	right *treeNode
}

func createTreeNode(v int) *treeNode {
	return &treeNode{
		v:     v,
		left:  nil,
		right: nil,
	}
}

type bst struct {
	root *treeNode
	size int
}

func CreateBst() *bst {
	return &bst{
		root: nil,
		size: 0,
	}
}
func (b *bst) Size() int {
	return b.size
}
func (b *bst) IsEmpty() bool {
	return b.size == 0
}
func (b *bst) AddNode(v int) {
	b.root = b.addNodeR(b.root, v)
}
func (b *bst) addNodeR(node *treeNode, v int) *treeNode {
	if node == nil {
		b.size++
		return createTreeNode(v)
	}
	if node.v > v { //left
		node.left = b.addNodeR(node.left, v)
	} else if node.v < v { //right
		node.right = b.addNodeR(node.right, v)
	}
	return node
}
func (b *bst) TraverFront() {
	b.traverFrontR(b.root)
}
func (b *bst) traverFrontR(node *treeNode) {
	if node != nil {
		fmt.Println(node.v)
		b.traverFrontR(node.left)
		b.traverFrontR(node.right)
	}
}
func (b *bst) TraverMiddle() {
	b.traverMiddleR(b.root)
}
func (b *bst) traverMiddleR(node *treeNode) {
	if node != nil {
		b.traverMiddleR(node.left)
		fmt.Println(node.v)
		b.traverMiddleR(node.right)
	}
}
func (b *bst) TraverBack() {
	b.traverBackR(b.root)
}
func (b *bst) traverBackR(node *treeNode) {
	if node != nil {
		b.traverBackR(node.left)
		b.traverBackR(node.right)
		fmt.Println(node.v)
	}
}
func (b *bst) TraverFloor() {
	b.traverFloor(b.root)
}
func (b *bst) traverFloor(node *treeNode) {
	lt := list.New()
	lt.PushBack(node)
	for lt.Len() > 0 {
		first := lt.Front()
		lt.Remove(lt.Front())
		fmt.Println(first.Value.(*treeNode).v)
		if first.Value.(*treeNode).left != nil {
			lt.PushBack(first.Value.(*treeNode).left)
		}
		if first.Value.(*treeNode).right != nil {
			lt.PushBack(first.Value.(*treeNode).right)
		}
	}
}
func (b *bst) Contains(v int) bool {
	return b.containsR(b.root, v)
}
func (b *bst) containsR(node *treeNode, v int) bool {
	if node == nil {
		return false
	}
	if node.v > v {
		return b.containsR(node.left, v)
	} else if node.v < v {
		return b.containsR(node.right, v)
	} else {
		return true
	}
}
func (b *bst) MinimalV() int {
	return b.minimalNodeR(b.root).v
}
func (b *bst) minimalNodeR(node *treeNode) *treeNode {
	if node.left != nil {
		return b.minimalNodeR(node.left)
	} else {
		return node
	}
}
func (b *bst) DeleteMinV() int {
	min := b.MinimalV()
	b.root = b.deleteMinNodeR(b.root)
	return min
}
func (b *bst) deleteMinNodeR(node *treeNode) *treeNode {
	if node.left != nil {
		node.left = b.deleteMinNodeR(node.left)
		return node
	} else {
		// node is minNode
		nright := node.right
		node.right = nil
		b.size--
		return nright
	}
}

func (b *bst) MaximunV() int {
	return b.maximunNodeR(b.root).v
}
func (b *bst) maximunNodeR(node *treeNode) *treeNode {
	if node.right != nil {
		return b.maximunNodeR(node.right)
	} else {
		return node
	}
}
func (b *bst) DeleteMaxV() int {
	max := b.MaximunV()
	b.root = b.deleteMaxNodeR(b.root)
	return max
}
func (b *bst) deleteMaxNodeR(node *treeNode) *treeNode {
	if node.right != nil {
		node.right = b.deleteMaxNodeR(node.right)
		return node
	} else {
		// node is maxNode
		nleft := node.left
		node.left = nil
		b.size--
		return nleft
	}
}
func (b *bst) DeleteV(v int) {
	b.root = b.deleteNodeR(b.root, v)
}
func (b *bst) deleteNodeR(node *treeNode, v int) *treeNode {
	if node == nil { //notfound
		return nil
	}
	if node.v == v { //found
		if node.left == nil {
			t := node.right
			node.right = nil
			return t
		}
		if node.right == nil {
			t := node.left
			node.left = nil
			return t
		}
		// two children is not nil below
		tmpNode := b.minimalNodeR(node.right)
		node.right = b.deleteMinNodeR(node.right)
		tmpNode.left = node.left
		tmpNode.right = node.right
		node.left = nil
		node.right = nil
		return tmpNode
	} else if node.v > v { //left
		node.left = b.deleteNodeR(node.left, v)
	} else { //right
		node.right = b.deleteNodeR(node.right, v)
	}
	return node
}
func (b *bst) Ceil(v int) int {
	return 0
}
func (b *bst) Floor(v int) int {
	return 0
}
func (b *bst) Depth(v int) int {
	return 0
}
func (b *bst) Rank(v int) int {
	return 0
}
